"""
尝试使用动态规划的思想解决
对于(())这样的形式，算不算有效括号，题目中未明说。
但考虑题目的难度，应该是算的，不然问题就太简单了。

dp[n]表示一个元组的集合。记录两个元素。
元组中的元素1表示“可用”左括号的数量；元素2表示连续括号数量。
或者分别用dpl和dpr进行记录。
以下给出3个例子：

	)	(	(	)	)
0	0	1	2	1	0
0	0	0	0	1	2
					
	)	(	)	(	)
0	0	1	0	1	0
0	0	0	1	1	2
					
	(	)	)	(	)
0	1	0	0	1	0
0	0	1	0	0	1

1. dpl[0]=dpr[0]=0
2. if s[n]='(' then dpl[n+1]=dpl[n]+1 dpr[n+1]=dpr[n]
3. if s[n]=')':
        if dpl[n]==0 then dpl[n+1]=dpr[n+1]=0
        else dpl[n+1]=dpl[n]-1 dpr[n+1]=dpr[n]+1
在这个遍历过程中，维护一个global_max表示最大括号数量

dp算法计算最大连续括号数量

回归根本。
如何判定一个字符串具备连续括号的特性：
1. 对每个字符进行遍历，从0开始维护一个sum，遇到左括号+1，遇到右括号-1。
2. 如果遍历的所有sum均>=0，且字符遍历到最后也是0，则认为该字符串具备连续括号的特性。

如果从一个字符串的开始位置算，计算最大连续括号的数量：
1. 维护数据同上；
2. 在上面数据的基础上，同时维护最后一次出现0的位置。如果出现负数，则直接不维护。
3. 最后一次出现0的位置，即从开始的最大连续括号的长度。

基于上述逻辑，如果对每个起始位置都维护这样的数据，并始终维护一个全局的最大连续括号长度。
则最后必定能获取字符串的最大连续括号长度。

这样做的时间复杂度，大约是O(n^2)

官方解法如下：
作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-valid-parentheses/solutions/314683/zui-chang-you-xiao-gua-hao-by-leetcode-solution/

其核心思想，还是如何用dp中的已知部分，加上推理，得到下一个未知的部分。

-   0   1   2   
-   (   )   )
0   0   2   0


"""
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        dp=[0]*len(s)

        def find_char(i:int)->str:
            return s[i] if i>=0 else None
            
        def find_dpv(i:int)->int:
            return dp[i] if i>=0 else 0

        max_dp=0
        for i in range(len(s)):
            # 构建dp[i+1]
            if s[i]=='(':
                continue
            if i-1<0:
                continue
            if s[i-1]=='(':
                dp[i]=find_dpv(i-2)+2
                max_dp=max(max_dp,dp[i])
                continue
            if dp[i-1]==0:
                continue
            # 此位置是去除已确定是括号的部分,前一个字符所在索引（可能为负数）
            bf=i-dp[i-1]-1
            bf_char=find_char(bf)
            if bf_char=='(':
                dp[i]=dp[i-1]+find_dpv(bf-1)+2
                max_dp=max(max_dp,dp[i])

        # print(dp)

        return max_dp

if __name__=='__main__':
    s='(())'

    sol=Solution()
    res=sol.longestValidParentheses(s)
    print(res)
    pass